package com.yao.code;

import java.util.PriorityQueue;

/**
 * @author yaoquanwei
 * @date 2021/8/24 21:42
 */
public class Code210824 {

    /**
     * 大顶
     */
    PriorityQueue<Integer> left;
    /**
     * 小顶
     */
    PriorityQueue<Integer> right;

    public Code210824() {
        left = new PriorityQueue<>((n1, n2) -> n2 - n1);
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if (left.size() + 1 < right.size()) {
            left.add(right.poll());
        }
    }

    public double findMedian() {
        if (right.size() > left.size()) {
            return right.peek();
        }
        return (double) (left.peek() + right.peek()) / 2;
    }

    /**
     * 剑指offer 40.最小的K个数
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num : arr) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && idx < k) {
                res[idx++] = num;
            }
            if (idx == k) {
                break;
            }
        }
        return res;
    }


}
